package cn.edu.thu.thss.algorithm.mathematics;

import java.math.BigInteger;

/**
 * 排列组合方面的基本工具类
 * 
 * @author EricPai
 */
public class CombinationUtils {

	/**
	 * 求组合数c(n, k)。即从n个数中取k个不同的数的组合方案。 如果为可重组合，则组合数为c(n + k - 1, k)
	 * @param n 总数
	 * @param k 取的个数
	 * 
	 * @return 组合方案数
	 */
	public BigInteger c(int n, int k) {
		BigInteger result = BigInteger.ZERO;
		if (k >= 0 && k <= n) {
			result = p(n, k).divide(factorial(k));
		}
		return result;
	}

	/**
	 * 求排列数p(n, k)。即从n个数中取k个不同的数的排列方案。
	 * @param n 总数
	 * @param k 取的个数
	 * 
	 * @return 排列方案数
	 */
	public BigInteger p(int n, int k) {
		BigInteger result = BigInteger.ZERO;
		if (k >= 0 && k <= n) {
			result = BigInteger.ONE;
			for (int i = 0; i < k; i++) {
				result = result.multiply(BigInteger.valueOf(n - i));
			}
		}
		return result;
	}

	/**
	 * 求n的阶乘。 
	 * @param n
	 * 
	 * @return n!
	 */
	public BigInteger factorial(int n) {
		BigInteger result = BigInteger.ZERO;
		if (n >= 0) {
			result = BigInteger.ONE;
			for (int i = 0; i < n; i++) {
				result = result.multiply(BigInteger.valueOf(i + 1));
			}
		}
		return result;
	}
}
